package review;

import org.junit.Test;

import java.util.Random;

/**
 * @Description
 * @Author Firenut
 * @Date 2022-11-16 16:12
 */
public class QuickSort {

    private static Random random = new Random(System.currentTimeMillis());

    @Test
    public void test() {
//        int[] nums = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        int[] nums = {2,3,4,4,4,5,6,7,1};
        quickSort(nums, 0, nums.length-1);
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int partiton = partition2(nums, left, right);
        quickSort(nums, left, partiton - 1);
        quickSort(nums, partiton + 1, right);
    }

    /**
     * 单路快排
     */
    public int partition(int[] nums, int left, int right) {
        int randIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randIndex);
        int pivot = nums[left];
        int j = left + 1;

//        [left,j) < pivot
//        [j,right]>= pivot
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, j);
                j++;
            }
        }
        swap(nums, left, j-1);
        return j-1;
    }

    /**
     * 双路快排
     */
    public int partition2(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int i = left + 1;
        int j = right;

//        while (i < j) {
        while (true){ //***
            while (i <= j && nums[i] < pivot) {//***
                i++;
            }
            while (i <= j && nums[j] > pivot) {//***
                j--;
            }
            //i找到一个大于等于pivot的值，j找到一个小于等于pivot的值
            if (i >= j) { //如果i==j,则该值等于pivot (这个条件不能卸载外层循环中)
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, left, j);
        return j;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}
